#include <iostream>
#include <algorithm>
#include <cstring>
const int MAXN = 100;
// 问题表示
int n = 5;
double W = 100;
struct NodeType
{
    double w;
    double v;
    double p;
    bool operator<(const NodeType &s) const
    {
        return p > s.p;
    }
};
NodeType A[] = {{0}, {10, 20}, {20, 30}, {30, 66}, {40, 40}, {50, 60}};
// 求解结果表示
double V;
double x[MAXN];

// 显示A数组的函数实现
void dispA()
{
    for (int i = 1; i <= n; i++)
    {
        std::cout << "物品 " << i << "：重量 = " << A[i].w << "，价值 = " << A[i].v << "，单位价值 = " << A[i].p << std::endl;
    }
}

void Knap()
{
    V = 0;
    double weight = W;
    std::memset(x, 0, sizeof(x));
    int i = 1;
    while (A[i].w < weight)
    {
        x[i] = 1;
        weight -= A[i].w;
        V += A[i].v;
        i++;
    }
    if (weight > 0)
    {
        x[i] = weight / A[i].w;
        V += x[i] * A[i].v;
    }
}
int main()
{
    for (int i = 1; i <= n; i++)
        A[i].p = A[i].v / A[i].w;
    std::cout << "(1) 排序前" << std::endl;
    dispA();
    std::sort(A + 1, A + n + 1);
    std::cout << "(2) 排序后" << std::endl;
    dispA();
    Knap();
    std::cout << "(3) 求解结果" << std::endl;
    std::cout << "x:[";
    for (int j = 1; j <= n; j++)
        std::cout << x[j] << ",";
    std::cout << x[n] << "]" << std::endl;
    std::cout << "  总价值 = " << V << std::endl;
    return 0;
}